var sortList = function (head) {
    if (head === null || head.next === null) return head
    let mid = getMid(head)
    let leftList = sortList(head)
    let rightList = sortList(mid)
    return merge(leftList, rightList)
};

function getMid(head) {
    let slow = head
    let fast = head.next
    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }
    let mid = slow.next
    slow.next = null
    return mid
}

function merge(left, right) {
    let dummy = new ListNode(0)
    let cur = dummy
    while (left && right) {
        if (left.val < right.val) {
            cur.next = left
            left = left.next
        } else {
            cur.next = right
            right = right.next
        }
        cur = cur.next
    }
    cur.next = left || right
    return dummy.next
}